// https://www.lintcode.com/problem/convert-sorted-list-to-binary-search-tree/

/**
 * Definition for ListNode.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int val) {
 *         this.val = val;
 *         this.next = null;
 *     }
 * }
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */


public class Solution {
    /*
     * @param head: The first node of linked list.
     * @return: a tree node
     */
    public TreeNode sortedListToBST(ListNode head) {
        // write your code here
        if (head == null) {
            return null;
        }
        ListNode prev = null;
        ListNode one = head;
        ListNode two = head.next;
        while (two != null) {
            two = two.next;
            if (two != null) {
                two = two.next;
                prev = one;
                one = one.next;
            }
        }
        ListNode rRoot = one.next;
        if (prev != null) {
            prev.next = null;
        }
        TreeNode root = new TreeNode(one.val);
        if (head != one) {
            root.left = sortedListToBST(head);
        }
        root.right = sortedListToBST(rRoot);
        return root;
    }
}